The exemplary embodiment relates to search algorithms, and more particularly to parallel and external-memory graph searches.
Searching a graph of combinatorial possibilities is a central technique in areas such as planning, combinatorial optimization, and model checking. For many problems in these areas, a bottleneck in the graph searching process is availability of internal memory of a computer system, such as random access memory (RAM). There is currently interest in using external memory, such as disk storage, to improve the scalability of graph search algorithms; however, access to external memory is orders of magnitude slower than RAM. To limit the number input/output (I/O) operations to the slower disk storage, two particular state space approaches have been developed that improve efficiency of graph search algorithms: delayed duplicate detection (DDD) and structured duplicate detection (SDD).
State-space search formalizes the states as nodes in a graph, and the actions as edges that connect one state to another. An optimal solution, one with the fewest steps or the lowest cost, to a planning problem corresponds to a path from the start state to a desired state. Because many solutions exist, nodes in a graph can be reached via a number of alternate paths from the start state, therefore it is often critical to detect duplicate states. Generally, duplicate states are stored in a list in RAM and the list is referenced prior to adding a new node. While this method ensures only a single copy of a state is stored, it also creates a memory bottleneck that prevents large problems from being solved. One solution is to use external memory disks to store previously explored nodes. As the cost per unit storage decreases, hard disks including solid state drives become cost-effective solutions to the memory bottleneck in graph search algorithms. However, the random access speed of disk is six orders of magnitude slower than that of RAM, making disk-based approaches to graph searches impractical. Indeed, all successful approaches to external-memory search make good use of the locality of the search graph to reduce the number of time-consuming I/O reads and writes. In parallel graph search algorithms, the same approach to leveraging graph locality is also effective in reducing the parallelization overhead such as communication and synchronization overhead between multiple threads.
There are a number of different types of algorithms used to perform graph searching, including Breadth-first search algorithms, uniform-cost search (e.g., Dijkstra's) algorithms, best-first search (e.g., A*) algorithms, among others. These and other related graph-search algorithms store generated nodes in memory in order to be able to detect duplicates and prevent node regeneration. The scalability of these graph-search algorithms can be dramatically increased by storing nodes in external memory, such as disk storage. However, as previously noted, because random access to a disk is several orders of magnitude slower than random access to an internal memory (e.g., RAM), benefits are obtained when external-memory graph search algorithms use duplicate-detection strategies that serialize disk access in a way that minimizes disk I/O.
The recently developed algorithms for external-memory graph search, e.g. hash-based DDD and SDD, rely on a hash function, or equivalently, a state-space projection function, that partitions the nodes of the state-space search graph into buckets of nodes that are stored as separate files on disk. For both hash-based DDD and SDD, the state-space projection function must satisfy the same criteria to ensure efficiency and scalability of the search algorithm. Firstly, the set of unique nodes in each bucket must fit in RAM. Secondly, there should not be many more buckets than necessary, which means nodes should be relatively evenly distributed among buckets and buckets should be relatively full. Lastly, search efficiency depends on how well the state-space projection function captures local structure in the graph. To accomplish this form any bucket of nodes, their successor nodes are found in only a small number of other buckets. Hash-based delayed duplicate detection leverages this form of local structure in order to interleave expansion and merging of nodes and structured duplicate detection uses it in its concept of duplicate detection scope.
Finding a state-space projection function that satisfies all of these criteria presents a challenge. In the past, handcrafted projection functions (at times called hash functions) were tailored to specific search domains with well-understood structure. More recently, appropriate projection function were automatically generated by heuristic-guided greedy searches of a corresponding space of possibilities. All previous work used static projection functions that did not change during the progress of the search. Static partitioning can capture local graph structure. However, for a static partition that captures local structure, it is difficult to predict in advance the number of nodes that will map to each bucket; in practice, the distribution of nodes to buckets can be very uneven. A randomized hash function creates a static partition that evenly distributes nodes among buckets. But it does not capture any local structure, since it allows nodes in one bucket to have successor nodes in any other random bucket. In short, it is difficult to design a projection function that both captures local structure and evenly distributes nodes among buckets.
The following describes a system and method which addresses the existing shortcomings and is believed to proved improvements to the present state of external memory graph searching.